package com.wangyadong.hobby.schedule.jobtask.dsa.binaryTree.da;

public class BinarySearchTree1<T> {


    private BinaryNode root;

    public boolean contains(T value, BinaryNode node) {
        if (node == null) {
            return false;
        }
        Comparable comparable = (Comparable) value;
        int compareResult = comparable.compareTo(node.value);
        if (compareResult < 0) {
            return contains(value, node.left);
        } else if (compareResult > 0) {
            return contains(value, node.right);
        } else {
            return true;
        }
    }


    public BinaryNode insert(T value, BinaryNode node) {
        if (node == null) {
            return new BinaryNode(value, null, null);
        }
        Comparable comparable = (Comparable) value;
        int compareResult = comparable.compareTo(node.value);
        if (compareResult < 0) {
            node.left = insert(value, node.left);
        } else if (compareResult > 0) {
            node.right = insert(value, node.right);
        } else {
            ;
        }
        return node;
    }


    public BinaryNode findMin(BinaryNode node) {
        if (node != null) {
            findMin(node.left);
        }
        return null;
    }

    public BinaryNode findMax(BinaryNode node) {
        if (node != null) {
            findMax(node.right);
        }
        return null;
    }


    private static class BinaryNode<T> {
        private T value;
        private BinaryNode left;
        private BinaryNode right;

        public BinaryNode(T value, BinaryNode left, BinaryNode right) {
            this.left = left;
            this.right = right;
            this.value = value;
        }
    }

    public BinaryNode insert(T value) {
        return this.root = insert(value, root);
    }

    public BinaryNode remove(T value) {
        return this.root = remove(value, root);
    }

    public BinaryNode remove(T value, BinaryNode node) {
        if (node == null) {
            return null;
        }
        Comparable comparable = (Comparable) value;
        int compareResult = comparable.compareTo(node.value);
        if (compareResult < 0) {
            node.left = remove(value, node.left);
        } else if (compareResult > 0) {
            node.right = remove(value, node.right);
        } else if (node.left != null && node.right != null) {
            //删除策略
            node.value = findMin(node.right).value;
            node = remove((T) node.value, node.right);
        } else {
            node = node.left != null ? node.left : node.right;
        }
        return node;
    }

    public static void main(String[] args) {
        BinarySearchTree1 binarySearchTree1 = new BinarySearchTree1();
        for (int i = 0; i < 10; i++) {
            binarySearchTree1.insert(i);
        }
        binarySearchTree1.remove(5);
        System.out.println(binarySearchTree1);
    }
}
